Blind 75-150
Array
- Two Sum - https://leetcode.com/problems/two-sum/
def twoSum(self, nums: List[int], target: int) -> List[int]:
num_dict = {}
for idx, num in enumerate(nums):
if target-num in num_dict:
return [idx, num_dict[target-num]]
num_dict[num] = idx
- Contains Duplicate - https://leetcode.com/problems/contains-duplicate/
def containsDuplicate(self, nums: List[int]) -> bool:
visit = {}
for num in nums:
if num in visit:
return True
visit[num] = True
- Product of Array Except Self - https://leetcode.com/problems/product-of-array-except-self/
# Prefix Prod * Postfix Prod
def productExceptSelf(self, nums: List[int]) -> List[int]:
prefix = 1
result = nums.copy()
for i in range(len(nums)):
result[i] = prefix
prefix *= nums[i]
postfix = 1
for i in range(len(nums)-1, -1, -1):
result[i] *= postfix
postfix *= nums[i]
return result
- Minimum Penalty - https://leetcode.com/problems/minimum-penalty-for-a-shop/description/
# Prefix + Postfix => Basically just count the occurence of N and occurence of Y before and after
def bestClosingTime(customers: str) -> int:
n_count = 0
pen = [0] * len(customers)
for i in range(len(customers)):
pen[i] += n_count
n_count += 1 if customers[i] == "N" else 0
y_count = 0
for i in range(len(customers) - 1, -1, -1):
y_count += 1 if customers[i] == "Y" else 0
pen[i] += y_count
min_pen = float("inf")
min_index = 0
for i in range(len(customers)):
if pen[i] < min_pen:
min_pen = pen[i]
min_index = i
if n_count < min_pen:
return len(customers)
return min_index
- Valid Anagram - https://leetcode.com/problems/valid-anagram/
def isAnagram(self, s: str, t: str) -> bool:
char_visit = {}
for char in s:
if char not in char_visit:
char_visit[char] = 0
char_visit[char] += 1
for char in t:
if char not in char_visit:
return False
char_visit[char] -= 1
if char_visit[char] == 0:
del char_visit[char]
return len(char_visit.keys()) == 0
- Group Anagrams - https://leetcode.com/problems/group-anagrams/
# Sort each string to create a key for each anagram group and save to a map
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
result = {}
for s in strs:
key = "".join(sorted(s))
if key not in result:
result[key] = [s]
else:
result[key].append(s)
return [val for val in result.values()]
- Top K Frequent Element - https://leetcode.com/problems/top-k-frequent-elements/
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
frequency = {}
for num in nums:
if num not in frequency:
frequency[num] = 0
frequency[num] +=1
items = [(-freq, num) for num, freq in frequency.items()]
heapq.heapify(items)
result = []
for i in range(k):
freq, num = heapq.heappop(items)
result.append(num)
return result
- Valid Sudoku - https://leetcode.com/problems/valid-sudoku/
# 3 dictionary to save value existence in each row, col and subbox
def isValidSudoku(self, board: List[List[str]]) -> bool:
row_map = {i: set() for i in range(0, 9)}
col_map = {i: set() for i in range(0, 9)}
box_map = {}
for row in range(len(board)):
for col in range(len(board[0])):
cur_val = board[row][col]
if cur_val != ".":
cur_row_val = row_map[row]
if cur_val in cur_row_val:
return False
cur_col_val = col_map[col]
if cur_val in cur_col_val:
return False
subbox_row, subbox_col = row//3, col//3
if (subbox_row, subbox_col) not in box_map:
box_map[(subbox_row, subbox_col)] = set()
cur_box_val = box_map[(subbox_row, subbox_col)]
if cur_val in cur_box_val:
return False
col_map[col].add(cur_val)
row_map[row].add(cur_val)
box_map[(subbox_row, subbox_col)].add(cur_val)
return True
- Longest Consecutive Sequence - https://leetcode.com/problems/longest-consecutive-sequence/
# Since the sequence doesnt need to follow order we can use hashmap for fast check if element exist
# Use dfs to check the length of val forward and backward, update the max
def longestConsecutive(self, nums: List[int]) -> int:
num_map = {}
result = 0
visit = set()
for num in nums:
num_map[num] = True
def count(val, direction, cnt):
next_val = val + direction
cnt+=1
visit.add(val)
if next_val in num_map:
cnt = count(next_val, direction, cnt)
return cnt
for num in nums:
if num not in visit:
up = count(num, 1, 0)
down = count(num, -1, 0)
total = up+down-1
result = max(total, result)
return result
# A much better approach with similar intuition but cleaner code and leverage caching to avoid re-calculation => Beat 92%
def longestConsecutive(self, nums: List[int]) -> int:
res = 0
counter = collections.Counter(nums)
visited = set()
for i in range(len(nums)):
if nums[i] in visited:
continue
l, r = nums[i], nums[i]
while l-1 in counter:
l -=1
visited.add(l)
while r+1 in counter:
r += 1
visited.add(r)
res = max(res, r - l + 1)
visited.add(nums[i])
return res
Two Pointer
- Valid Palindrome - https://leetcode.com/problems/valid-palindrome/
# 2 pointer
def isPalindrome(self, s: str) -> bool:
s = s.lower()
s = ''.join(filter(str.isalnum, s))
left, right = 0, len(s) - 1
while left < right:
if s[left] == s[right]:
left+=1
right-=1
else:
return False
return True
- Two Sum 2 Input Array is Sorted - https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left, right = 0, len(numbers) - 1
while left < right:
cur_sum = numbers[left] + numbers[right]
if cur_sum == target:
return [left+1, right+1]
elif cur_sum > target:
right -=1
elif cur_sum < target:
left +=1
- 3Sum - https://leetcode.com/problems/3sum/
Use this trick [[Cheap Trick#^73797d| Handle duplication ]]
# O(n^2) solution
# Sort and then nested for loop
# At each step check for duplicate with previous value (thats why we need to sort)
# At each step use 2 pointer to find the remaining 2 sum
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
result = []
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i-1]:
continue
left, right = i+1, len(nums) - 1
while left < right:
cur_sum = nums[i] + nums[left] + nums[right]
if cur_sum < 0:
left +=1
elif cur_sum > 0:
right -=1
elif cur_sum == 0:
result.append([nums[i], nums[left], nums[right]])
left +=1
while left < right and nums[left] == nums[left-1]:
left +=1
return result
- Container With Most Water - https://leetcode.com/problems/container-with-most-water/
# 2 pointer, move the pointer where the height is smaller for a chance to get better height
# Update max at each step
def maxArea(self, height: List[int]) -> int:
result = float("-inf")
left, right = 0, len(height) -1
while left < right:
cur_total = min(height[left], height[right]) * (right-left)
result = max(cur_total, result)
if height[right] <= height[left]:
right -=1
elif height[left] < height[right]:
left +=1
return result
- Trapping Rain Water - https://leetcode.com/problems/trapping-rain-water/
Sliding Window
- Best Time to Buy and Sell Stock - https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
def maxProfit(self, prices: List[int]) -> int:
result = float("-inf")
min_so_far = prices[0]
for price in prices:
cur = price - min_so_far
result = max(result, cur)
min_so_far = min(min_so_far, price)
return result
- Longest Substring Without Repeating Characters - https://leetcode.com/problems/longest-substring-without-repeating-characters/
# Keep a moving set to keep track of what currently in the substring
# If meet duplicate remove that from the set and increase left pointer
def lengthOfLongestSubstring(self, s: str) -> int:
char_set = set()
res = 0
left = 0
for right in range(len(s)):
while s[right] in char_set:
char_set.remove(s[left])
left +=1
char_set.add(s[right])
res = max(res, right-left+1)
return res
- Longest Repeating Character Replacement - https://leetcode.com/problems/longest-repeating-character-replacement/
- Minimum Window Substring - https://leetcode.com/problems/minimum-window-substring/
- Permutation in String - https://leetcode.com/problems/permutation-in-string/
- Sliding Window Maximum - https://leetcode.com/problems/sliding-window-maximum/
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
res = []
queue = []
left = right = 0
while right < len(nums):
while queue and nums[queue[-1]] < nums[right]:
queue.pop()
queue.append(right)
if left > queue[0]:
queue.pop(0)
if right + 1 >= k:
res.append(nums[queue[0]])
left+=1
right+=1
return res
Stack
- Valid Parentheses - https://leetcode.com/problems/valid-parentheses/
# stack
def isValid(self, s: str) -> bool:
if len(s) == 1:
return False
pairs = {
")": "(",
"]": "[",
"}": "{"
}
stack = []
for bracket in s:
if bracket not in pairs.keys():
stack.append(bracket)
else:
if len(stack) == 0 or stack[-1] != pairs[bracket]:
return False
else:
stack.pop()
return len(stack) == 0
- Min Stack - https://leetcode.com/problems/min-stack/
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val: int) -> None:
self.stack.append(val)
if self.min_stack:
new_min = min(self.min_stack[-1], val)
if new_min == val:
self.min_stack.append(val)
else:
self.min_stack.append(val)
def pop(self) -> None:
num = self.stack.pop()
if num == self.min_stack[-1]:
self.min_stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_stack[-1]
- Evaluate Reverse Polish Notation - https://leetcode.com/problems/evaluate-reverse-polish-notation/
def evalRPN(self, tokens: List[str]) -> int:
stack = []
operations = ["+", "-", "*", "/"]
result = 0
for token in tokens:
if token not in operations:
stack.append(token)
else:
num1 = stack.pop()
num2 = stack.pop()
res = 0
if token == "+":
res = int(num2) + int(num1)
elif token == "-":
res = int(num2) - int(num1)
elif token == "*":
res = int(num2) * int(num1)
elif token == "/":
res = int(num2) / int(num1)
if res >= 0:
res = math.floor(res)
else:
res = math.ceil(res)
stack.append(str(res))
return int(stack[-1])
- Generate Parentheses - https://leetcode.com/problems/generate-parentheses/
# Backtracking, at each step we can add an opening if the number of opening is less than n or add a closing if the number of closing is less than the number of opening. We can use backtracking and check for each option
def generateParenthesis(self, n: int) -> List[str]:
result = []
working = []
def dfs(openCnt, closedCnt):
if openCnt == n and closedCnt == n:
result.append("".join(working))
return
if openCnt < n:
working.append("(")
dfs(openCnt+1, closedCnt)
working.pop()
if closedCnt < openCnt:
working.append(")")
dfs(openCnt, closedCnt+1)
working.pop()
dfs(0, 0)
return result
- Daily Temperature - https://leetcode.com/problems/daily-temperatures/
# Monotonic Stack
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
res = [0] * len(temperatures)
stack = []
for i, temp in enumerate(temperatures):
while stack and temp > stack[-1][0]:
top_temp, top_i = stack.pop()
res[top_i] = i - top_i
stack.append((temp, i))
return res
- Car Fleet - https://leetcode.com/problems/car-fleet/
def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
pair = [(pos, speed) for pos, speed in zip(position, speed)]
pair.sort(reverse=True)
stack = []
for pos, speed in pair:
stack.append((target-pos)/speed)
if len(stack) >=2 and stack[-1] <= stack[-2]:
stack.pop()
return len(stack)
- Largest Rectangle in Histogram - https://leetcode.com/problems/largest-rectangle-in-histogram/
Binary Search
- Ref: [[Binary Search]]
- Binary Search - https://leetcode.com/problems/binary-search/
def search(self, nums: List[int], target: int) -> int:
if len(nums) == 1:
if nums[0] != target:
return -1
else:
return 0
left, right = 0, len(nums)-1
while left <= right:
mid = (left+right)//2
if target < nums[mid]:
right = mid -1
elif target > nums[mid]:
left = mid +1
elif target == nums[mid]:
return mid
return -1
- Search A 2d Matrix - https://leetcode.com/problems/search-a-2d-matrix/
# The matrix is sorted each row and each cols
# Only need to find a row whose range may contain the target
# Perform binary search on that row only
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
target_row = None
for row in matrix:
start, end = row[0], row[-1]
if start <= target and target <= end:
target_row = row
break
if not target_row:
return False
left, right = 0, len(target_row)-1
while left <= right:
mid = (right+left)//2
if target < target_row[mid]:
right = mid -1
elif target > target_row[mid]:
left = mid + 1
elif target == target_row[mid]:
return True
return False
- Koko eating Banana - https://leetcode.com/problems/koko-eating-bananas/
# The search space is the eating speed, at each step check if the current speed is possible to finish all piles if yes then check if it is possible to lower the speed down by checking the left side of mid
def minEatingSpeed(self, piles: List[int], h: int) -> int:
def condition(k):
hour = 0
for pile in piles:
if k >= pile:
hour +=1
else:
hour += pile//k
if pile%k:
hour += 1
return hour <= h
left, right = 1, max(piles)
while left < right:
mid = left + (right-left)//2
if condition(mid):
right = mid
else:
left = mid + 1
return left
- Find Minimum in Rotated Sorted Array - https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
# The requirement is O(log n) => Binary Search
# The minimum will be the first index of the array before pivot
# The assumption is that after pivot the left subarray will be larger than the right array
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) -1
while nums[left] > nums[right]:
middle = (right+left)//2
if nums[middle] > nums[right]:
left = middle+1
elif nums[middle] < nums[right]:
right = middle
return min(nums[left], nums[right])
- Search in Rotated Sorted Array - https://leetcode.com/problems/search-in-rotated-sorted-array/
# Find the pivot index => With the pivot we can split the array into 2 subarray sorted in ascending order => Perform BS in each
def search(self, nums: List[int], target: int) -> int:
def bs(left, right):
while left <= right:
middle = left + (right-left)//2
if nums[middle] < target:
left = middle + 1
elif nums[middle] > target:
right = middle - 1
else:
return middle
return -1
left, right = 0, len(nums) - 1
while nums[left] > nums[right]:
middle = left + (right-left)//2
if nums[middle] > nums[right]:
left = middle + 1
elif nums[middle] < nums[right]:
right = middle
minIdx = 0
if nums[left] > nums[right]:
minIdx = right
else:
minIdx = left
left = bs(0, minIdx-1)
right = bs(minIdx, len(nums)-1)
if left != -1:
return left
if right != -1:
return right
return -1
- https://leetcode.com/problems/time-based-key-value-store/
- https://leetcode.com/problems/median-of-two-sorted-arrays/
Binary
- Sum of Two Integers - https://leetcode.com/problems/sum-of-two-integers/
- Number of 1 Bits - https://leetcode.com/problems/number-of-1-bits/
- Counting Bits - https://leetcode.com/problems/counting-bits/
- Missing Number - https://leetcode.com/problems/missing-number/
- Reverse Bits - https://leetcode.com/problems/reverse-bits/
Dynamic Programming
- Climbing Stairs - https://leetcode.com/problems/climbing-stairs/
# DP distinct ways
def climbStairs(self, n: int) -> int:
@lru_cache(None)
def dp(state):
if state <= 2:
return state
ways = dp(state-1) + dp(state-2)
return ways
return dp(n)
def climbStairs(self, n: int) -> int:
if n <=2:
return n
table = [0] * (n+1)
table[1] = 1
table[2] = 2
for i in range(3, n+1):
table[i] = table[i-1] + table[i-2]
return table[n]
- Coin Change - https://leetcode.com/problems/coin-change/
# DP min path to reach result
def coinChange(self, coins: List[int], amount: int) -> int:
@lru_cache(None)
def dp(amount):
if amount == 0:
return 0
if amount < 0:
return float("inf")
res = []
for val in coins:
res.append(dp(amount-val))
return 1 + min(res)
res = dp(amount)
if res == float("inf"):
return -1
return res
def coinChange(self, coins: List[int], amount: int) -> int:
count = [float("inf")] * (amount+1)
count[0] = 0
for val in coins:
if val in range(amount+1):
count[val] = 1
for i in range(1, amount+1):
for val in coins:
if i - val >= 0:
count[i] = min(count[i], 1 + count[i-val])
if count[amount] == float("inf"):
return -1
return count[amount]
- Longest Increasing Subsequence - https://leetcode.com/problems/longest-increasing-subsequence/
[[DP#Longest Increasing Subsequence]] ^850c48
# Travel from right to left so that we have case like 1,5,3 already handled as when we process a number, we know that all the number after it has already been processed
def lengthOfLIS(self, nums: List[int]) -> int:
longest_ahead = [1] * len(nums)
for i in range(len(nums) -1, -1, -1):
for j in range(i+1, len(nums)):
if nums[i] < nums[j]:
longest_ahead[i] = max(longest_ahead[i], 1 + longest_ahead[j])
return max(longest_ahead)
- Longest Common Subsequence - https://leetcode.com/problems/longest-common-subsequence/
# Construct a mxn matrix where m is the len of text1 and n is len of text2
# at cell [i][j] means that the longest common from i=>m-1 and j=>n-1
# If curRow == curCol means that the current longest is 1 + whatever behind it, which is at [i+1][j+1]
# If not then it is the max of 1 row down or 1 col right, means that the current longest will not contain the current cell, so we have to check behind it
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
dp = [[0 for j in range(len(text2) + 1)] for i in range(len(text1)+1)]
for i in range(len(text1)-1, -1, -1):
for j in range(len(text2) -1, -1, -1):
if text1[i] == text2[j]:
dp[i][j] = 1 + dp[i+1][j+1]
else:
dp[i][j] = max(dp[i+1][j], dp[i][j+1])
return dp[0][0]
- Word Break Problem - https://leetcode.com/problems/word-break/
# Notice that we may have to make a decision between multiple kinda similar word in
# the dictionary, that's where dp come in as we check every word in the dictionary
# and return after we have solved all the subproblem
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
@lru_cache(None)
def dp(index):
if index >= len(s):
return True
check = False
for word in wordDict:
wordLength = len(word)
if s[index:index+wordLength] == word:
check = check or dp(index+wordLength)
return check
return dp(0)
- Combination Sum - https://leetcode.com/problems/combination-sum-iv/ ^3a0803
# DP distinct ways
def combinationSum4(self, nums: List[int], target: int) -> int:
@lru_cache(None)
def dp(target):
if target < 0:
return 0
if target == 0:
return 1
res = 0
for num in nums:
res += dp(target-num)
return res
return dp(target)
- House Robber - https://leetcode.com/problems/house-robber/
# DP max number of path to reach target
def rob(self, nums: List[int]) -> int:
@lru_cache(None)
def dp(index, money):
if index > len(nums) - 1:
return money
rob = dp(index+2, money + nums[index])
no_rob = dp(index+1, money)
return max(rob, no_rob)
return dp(0, 0)
def rob(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
if len(nums) == 1:
return nums[0]
gain = [0] * len(nums)
gain[0] = nums[0]
gain[1] = max(nums[1], nums[0])
for i in range(2, len(nums)):
gain[i] = max(gain[i-1], nums[i] + gain[i-2])
return gain[-1]
- House Robber II - https://leetcode.com/problems/house-robber-ii/
# DP, use tabulation method of House Robber 1 as helper and run it 2 times for 2 input set one with the first house but not the last, and the other with the last but not the first
# Or use normal top down which need an additional variable to save the information if we robbed the first house which disallow us from robbing the last house
def rob(self, nums: List[int]) -> int:
if len(nums) <= 1:
return sum(nums)
@lru_cache(None)
def dp(index, total, has_first):
if index >= len(nums):
return total
if index == len(nums) - 1 and has_first:
return total
rob = dp(index + 2, total + nums[index], has_first)
if index == 0:
has_first = False
not_rob = dp(index+1, total, has_first)
return max(rob, not_rob)
return dp(0, 0, True)
def rob(self, nums: List[int]) -> int:
def helper(nums):
if len(nums) == 0:
return 0
if len(nums) == 1:
return nums[0]
gain = [0] * len(nums)
gain[0] = nums[0]
gain[1] = max(nums[1], nums[0])
for i in range(2, len(nums)):
gain[i] = max(gain[i-1], nums[i] + gain[i-2])
return gain[-1]
return max(nums[0], helper(nums[:-1]), helper(nums[1:]))
- Decode Ways - https://leetcode.com/problems/decode-ways/
# Have to handle case where the 2 value isn't within range(26)
def numDecodings(self, s: str) -> int:
def helper(left, right):
if int(s[left:right]) >=1 and int(s[left:right]) <= 26:
return True
return False
@lru_cache(None)
def dp(index):
if index > len(s):
return 0
if index == len(s):
return 1
if s[index] == "0":
return 0
if index == len(s) - 1:
return 1
res = 0
if helper(index, index+1):
res += dp(index+1)
if helper(index,index+2):
res += dp(index+2)
return res
return dp(0)
- Unique Paths - https://leetcode.com/problems/unique-paths/
# classic distinc ways DP
def uniquePaths(self, rows: int, cols: int) -> int:
@lru_cache(None)
def dp(row, col):
if row not in range(rows) or col not in range(cols):
return 0
if row == rows-1 and col == cols-1:
return 1
return dp(row+1, col) + dp(row, col+1)
return dp(0, 0)
- Longest Palindromic Substring - https://leetcode.com/problems/longest-palindromic-substring/
# Middle out to check for palindrome to reduce overall complexity
def longestPalindrome(self, s: str) -> str:
res = ""
for i in range(len(s)):
left, right = i, i
while left >= 0 and right < len(s) and s[left] == s[right]:
if (right-left+1) > len(res):
res = s[left:right+1]
left -=1
right +=1
left, right = i, i+1
while left >= 0 and right < len(s) and s[left] == s[right]:
if (right-left+1) > len(res):
res = s[left:right+1]
left -=1
right +=1
return res
- Palindromic Substrings - https://leetcode.com/problems/palindromic-substrings/
# DP to check Palindrome instead of regular 2 pointer
# No need to try for O(n) solution when working with DP string
def countSubstrings(self, s: str) -> int:
@lru_cache(None)
def helper(left, right):
if left > right:
return True
if s[left] != s[right]:
return False
return helper(left+1, right-1)
n = len(s)
res = 0
for i in range(n):
for j in range(i, n):
if helper(i, j):
res +=1
return res
- Maximum Product Subarray - https://leetcode.com/problems/maximum-product-subarray/
# DP 2 choices take current num or not take current num
def maxProduct(self, nums: List[int]) -> int:
res = float("-inf")
@lru_cache(None)
def dp(index, product):
nonlocal res
if index >= len(nums):
return product
res = max(res, product*nums[index])
take = dp(index+1, product*nums[index])
not_take = dp(index+1, 1)
return max(take, not_take)
dp(0,1)
return res
def maxProfit(self, prices: List[int]) -> int:
@lru_cache(None)
def dp(day, has_stock, cd):
if day >= len(prices):
return 0
action_gain = 0
if not cd:
if has_stock:
action_gain = prices[day] + dp(day+1, False, True)
else:
action_gain = -prices[day] + dp(day+1, True, False)
noaction_gain = dp(day+1, has_stock, False)
return max(action_gain, noaction_gain)
return dp(0, False, False)
# DP at each step have 2 choices take the current coin value or update the coin value
def change(self, target: int, coins: List[int]) -> int:
@lru_cache(None)
def dp(coinIndex, amount):
if amount == target:
return 1
if amount > target:
return 0
if coinIndex == len(coins):
return 0
take = dp(coinIndex, amount + coins[coinIndex])
not_take = dp(coinIndex+1, amount)
return take + not_take
return dp(0, 0)
def findTargetSumWays(self, nums: List[int], target: int) -> int:
@lru_cache(None)
def dp(index, cur_sum):
if index >= len(nums) and cur_sum == target:
return 1
if index >= len(nums) and cur_sum != target:
return 0
positive = dp(index+1, cur_sum + nums[index])
negative = dp(index+1, cur_sum - nums[index])
return positive + negative
return dp(0, 0)
- https://leetcode.com/problems/interleaving-string/
- https://leetcode.com/problems/longest-increasing-path-in-a-matrix/
- https://leetcode.com/problems/distinct-subsequences/
- https://leetcode.com/problems/edit-distance/
- https://leetcode.com/problems/burst-balloons/
- https://leetcode.com/problems/min-cost-climbing-stairs/
def minCostClimbingStairs(self, cost: List[int]) -> int:
@lru_cache(None)
def dp(pos):
if pos >= len(cost):
return 0
one = cost[pos] + dp(pos+1)
two = cost[pos] + dp(pos+2)
return min(one, two)
return min(dp(0), dp(1))
- https://leetcode.com/problems/partition-equal-subset-sum/
- https://leetcode.com/problems/regular-expression-matching/
Greedy
- Jump Game - https://leetcode.com/problems/jump-game/
def canJump(self, nums: List[int]) -> bool:
@lru_cache(None)
def dp(index):
if index >= len(nums) - 1:
return True
max_jump = nums[index]
for i in range(1, max_jump+1):
if dp(index+i):
return True
return False
return dp(0)
def canJump(self, nums: List[int]) -> bool:
goal = len(nums) - 1
right = len(nums) - 2
while right >= 0:
if right + nums[right] >= goal:
goal = right
right -=1
return goal == 0
- Maximum Subarray - https://leetcode.com/problems/maximum-subarray/
def maxSubArray(self, nums: List[int]) -> int:
result = float("-inf")
@lru_cache(None)
def dp(index, cur_sum):
nonlocal result
if index >= len(nums):
return cur_sum
result = max(result, cur_sum + nums[index])
take = dp(index+1, cur_sum + nums[index])
not_take = dp(index+1, 0)
return max(take, not_take)
dp(0, 0)
return result
def maxSubArray(self, nums: List[int]) -> int:
table = [0] * len(nums)
table[0] = nums[0]
for i in range(1, len(nums)):
table[i] = max(nums[i], table[i-1] + nums[i])
return max(table)
def jump(self, nums: List[int]) -> int:
res = 0
target = len(nums) - 1
index = 0
while target > 0:
if index + nums[index] >= target:
target = index
index = 0
res +=1
else:
index +=1
return res
```python
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
gain = [i-j for i, j in zip(gas, cost)]
start, end = len(gas)-1, 0
total = gain[-1]
while start>=end:
while total < 0 and start >= end:
start -=1
total += gain[start]
if start == end:
return start
total += gain[end]
end +=1
return -1
- https://leetcode.com/problems/hand-of-straights/
- https://leetcode.com/problems/merge-triplets-to-form-target-triplet/
- https://leetcode.com/problems/partition-labels/
- https://leetcode.com/problems/valid-parenthesis-string/
## Graph
- Clone Graph - [https://leetcode.com/problems/clone-graph/](https://leetcode.com/problems/clone-graph/)
```python
def cloneGraph(self, root: 'Node') -> 'Node':
if not root:
return
visit = {}
def bfs(node):
if node.val in visit:
return visit[node.val]
new_node = Node(node.val)
visit[node.val] = new_node
for nb in node.neighbors:
new_node.neighbors.append(bfs(nb))
return new_node
return bfs(root)
- Course Schedule - https://leetcode.com/problems/course-schedule/
# Topological sort with different value in visit to indicate different state in processing
def canFinish(self, numCourses: int, pres: List[List[int]]) -> bool:
adj = {i:[] for i in range(numCourses)}
for a,b in pres:
adj[b].append(a)
result = []
visit = [0] * (numCourses+1)
def bfs(course):
visit[course] = 1
for nb in adj[course]:
if visit[nb] == 1:
return False
elif visit[nb] == 0 and bfs(nb) is False:
return False
result.insert(0, course)
visit[course] = 2
return True
for i in range(numCourses):
if visit[i] == 0:
if bfs(i) is False:
return False
return len(result) == numCourses
- Course Schedule 2 - https://leetcode.com/problems/course-schedule-ii/
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
visit = [0] * (numCourses+1)
adj = {i: [] for i in range(numCourses)}
res = []
for a, b in prerequisites:
adj[b].append(a)
def bfs(course):
visit[course] = 1
for nb in adj[course]:
if visit[nb] == 1:
return False
elif visit[nb] == 0 and bfs(nb) is False:
return False
res.insert(0, course)
visit[course] = 2
return True
for course in range(numCourses):
if visit[course] == 0:
if bfs(course) is False:
return []
return res
- Rotting Oranges - https://leetcode.com/problems/rotting-oranges/
def orangesRotting(self, grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
queue = []
fresh = 0
result = 0
for row in range(rows):
for col in range(cols):
if grid[row][col] == 2:
queue.append((row, col))
elif grid[row][col] == 1:
fresh +=1
if not fresh:
return result
while queue:
if not fresh:
break
len_q = len(queue)
result +=1
for i in range(len_q):
cur_row, cur_col = queue.pop(0)
for row_dir, col_dir in directions:
adj_row, adj_col = cur_row + row_dir, cur_col + col_dir
if (
adj_row in range(rows) and
adj_col in range(cols)
):
if grid[adj_row][adj_col] == 1:
grid[adj_row][adj_col] = 2
fresh -=1
queue.append((adj_row, adj_col))
return result if fresh == 0 else -1
- Surrounded Regions - https://leetcode.com/problems/surrounded-regions/
# Traverse and mark all cell that should not be flip (adjacent to border) as visited, and traverse again to flip all cell that can be flip
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
visit = {}
rows, cols = len(board), len(board[0])
def bfs(row, col, flip = False):
if ((row, col) not in visit and board[row][col] == "O"):
visit[(row, col)] = True
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
if flip == True:
board[row][col] = "X"
for row_dir, col_dir in directions:
next_row, next_col = row + row_dir, col + col_dir
if (next_row in range(rows) and
next_col in range(cols) and
(next_row, next_col) not in visit and
board[next_row][next_col] == "O"
):
bfs(next_row, next_col, flip)
for row in range(rows):
bfs(row, 0)
bfs(row, cols-1)
for col in range(cols):
bfs(0, col)
bfs(rows-1, col)
for row in range(rows):
for col in range(cols):
if (row, col) not in visit and board[row][col] == "O":
bfs(row, col, True)
- Max Area of Island - https://leetcode.com/problems/max-area-of-island/
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
if not grid:
return 0
visit = {}
max_area = 0
rows, cols = len(grid), len(grid[0])
def bfs(row, col):
cur_area = 0
queue = [(row, col)]
visit[(row, col)] = True
cur_area +=1
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while queue:
cur_row, cur_col = queue.pop(0)
for row_dir, col_dir in directions:
next_row, next_col = cur_row + row_dir, cur_col + col_dir
if (next_row in range(rows) and
next_col in range(cols) and
grid[next_row][next_col] == 1 and
(next_row, next_col) not in visit
):
queue.append((next_row, next_col))
visit[(next_row, next_col)] = True
cur_area +=1
return cur_area
for row in range(rows):
for col in range(cols):
if (row, col) not in visit and grid[row][col] == 1:
max_area = max(max_area, bfs(row, col))
return max_area
- Pacific Atlantic Water Flow - https://leetcode.com/problems/pacific-atlantic-water-flow/
# BFS with directions
# Instead of move each cell in rows and cols, we move from the the 4 side in
# That means to call bfs on the first and last row, and first and last column
def pacificAtlantic(self, grid: List[List[int]]) -> List[List[int]]:
rows, cols = len(grid), len(grid[0])
result = []
pacific_check, atlantic_check = {}, {}
def bfs(row, col, visit):
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
visit[(row, col)] = True
for row_dir, col_dir in directions:
next_row, next_col = row + row_dir, col + col_dir
if ((next_row, next_col) not in visit and
next_row in range(rows) and
next_col in range(cols) and
grid[row][col] <= grid[next_row][next_col]
):
bfs(row+row_dir, col+col_dir, visit)
return
for col in range(cols):
bfs(0, col, pacific_check)
bfs(rows-1, col, atlantic_check)
for row in range(rows):
bfs(row, 0, pacific_check)
bfs(row, cols-1, atlantic_check)
for row in range(rows):
for col in range(cols):
if (row, col) in pacific_check and (row, col) in atlantic_check:
result.append([row, col])
return result
- Number of Islands - https://leetcode.com/problems/number-of-islands/
# Classic bfs graph matrix with directions
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
visit = {}
count = 0
def bfs(row, col):
queue = [(row, col)]
visit[(row, col)] = True
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while queue:
cur_row, cur_col = queue.pop(0)
for row_dir, col_dir in directions:
next_row, next_col = cur_row + row_dir, cur_col + col_dir
if (
next_row in range(rows) and
next_col in range(cols) and
grid[next_row][next_col] == "1" and
(next_row, next_col) not in visit
):
queue.append((next_row, next_col))
visit[(next_row, next_col)] = True
for row in range(rows):
for col in range(cols):
if (row, col) not in visit and grid[row][col] == "1":
bfs(row, col)
count +=1
return count
Advanced Graph
- https://leetcode.com/problems/reconstruct-itinerary/
- https://leetcode.com/problems/min-cost-to-connect-all-points/
- https://leetcode.com/problems/network-delay-time/
- https://leetcode.com/problems/swim-in-rising-water/
- https://leetcode.com/problems/cheapest-flights-within-k-stops/
Interval
- Insert Interval - https://leetcode.com/problems/insert-interval/
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
res = []
for i in range(len(intervals)):
if newInterval[1] < intervals[i][0]:
res.append(newInterval)
return res + intervals[i:]
elif newInterval[0] > intervals[i][1]:
res.append(intervals[i])
else:
newInterval = [min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])]
res.append(newInterval)
return res
- Merge Intervals - https://leetcode.com/problems/merge-intervals/
intervals.sort(key=lambda x:x[0])
output = [intervals[0]]
for start, end in intervals[1:]:
lastEnd = output[-1][1]
if start <= lastEnd:
output[-1][1] = max(lastEnd, end)
else:
output.append([start, end])
return output
- Non-overlapping Intervals - https://leetcode.com/problems/non-overlapping-intervals/
intervals.sort(key=lambda x: x[0])
res = 0
stack = [intervals[0]]
for start, end in intervals[1:]:
lastStart, lastEnd = stack[-1]
if start >= lastEnd:
stack.append((start, end))
else:
if end <= lastEnd:
stack.pop()
stack.append((start, end))
res+=1
return res
- Minimum Interval to Include Each query - https://leetcode.com/problems/minimum-interval-to-include-each-query/
Linked List
- Reverse a Linked List - https://leetcode.com/problems/reverse-linked-list/
# Have to memorize
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev = None
while head:
cur_next = head.next
head.next = prev
prev = head
head = cur_next
return prev
- Detect Cycle in a Linked List - https://leetcode.com/problems/linked-list-cycle/
# Fast and slow pointer
def hasCycle(self, head: Optional[ListNode]) -> bool:
if head is None or head.next is None:
return False
slow, fast = head, head
while fast.next is not None and fast.next.next is not None:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
- Merge Two Sorted Lists - https://leetcode.com/problems/merge-two-sorted-lists/
# Dummy node trick
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0)
head = dummy
while list1 and list2:
if list1.val <= list2.val:
head.next = list1
list1 = list1.next
else:
head.next = list2
list2 = list2.next
head = head.next
if list1:
head.next = list1
if list2:
head.next = list2
return dummy.next
- Merge K Sorted Lists - https://leetcode.com/problems/merge-k-sorted-lists/
- Remove Nth Node From End Of List - https://leetcode.com/problems/remove-nth-node-from-end-of-list/
# Dummy node trick
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
right = head
while n > 0 and right:
right = right.next
n -=1
dummy = ListNode(0, head)
left = dummy
while right:
left = left.next
right = right.next
left.next = left.next.next
return dummy.next
- Reorder List - https://leetcode.com/problems/reorder-list/
# Find the middle node
# Reverse the second half
# Merge the 2 half alternatively
def reorderList(self, head: Optional[ListNode]) -> None:
"""
Do not return anything, modify head in-place instead.
"""
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
middle = slow.next
slow.next = None
prev = None
while middle:
cur_next = middle.next
middle.next = prev
prev = middle
middle = cur_next
head1 = head
head2 = prev
while head1 and head2:
next1, next2 = head1.next, head2.next
head1.next = head2
if next1:
head2.next = next1
head1, head2 = next1, next2
- Copy List With Random Pointerhttps://leetcode.com/problems/copy-list-with-random-pointer/
- Add two numbers - https://leetcode.com/problems/add-two-numbers/
```python
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
carry = 0
dummy = ListNode()
cur_node = dummy
while l1 or l2 or carry:
v1 = l1.val if l1 else 0
v2 = l2.val if l2 else 0
cur_val = v1 + v2 + carry
carry = cur_val // 10
val = cur_val % 10
cur_node.next = ListNode(val)
cur_node = cur_node.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy.next
- LRU Cache - https://leetcode.com/problems/lru-cache/
# Use doubly linked list to keep track of least recent use and most recent use
# The least recent use will be the head and most recent use will be the tail
# Whenever need to update the LRU and MRU, just need update the head or tail of the linked list, which is O(1)
# Use a hashmap with key point to a node for fast checkup
# Left, right pointer is a dummy pointer that point to LRU and MRU, this makes code cleaner
class Node:
def __init__(self, key, val):
self.key, self.val = key, val
self.prev, self.next = None, None
class LRUCache:
def __init__(self, capacity: int):
self.cache = {}
self.cap = capacity
self.left, self.right = Node(0, 0), Node(0, 0)
self.left.next = self.right
self.right.prev = self.left
def remove(self, node):
prev, nxt = node.prev, node.next
prev.next, nxt.prev = nxt, prev
def insert(self, node):
prev, nxt = self.right.prev, self.right
prev.next = nxt.prev = node
node.next, node.prev = nxt, prev
def get(self, key: int) -> int:
if key in self.cache:
node = self.cache[key]
self.remove(node)
self.insert(node)
return node.val
return -1
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.remove(self.cache[key])
self.cache[key] = Node(key, value)
self.insert(self.cache[key])
if len(self.cache) > self.cap:
lru = self.left.next
self.remove(lru)
del self.cache[lru.key]
- Merge K Sorted List - https://leetcode.com/problems/merge-k-sorted-lists/
- Reverse Nodes in K group - https://leetcode.com/problems/reverse-nodes-in-k-group/
Matrix/Math
- Set Matrix Zeroes - https://leetcode.com/problems/set-matrix-zeroes/
# Use set to store all rows, cols that has a 0. Iterate 2nd times and update all cell that has either row or col in the set to 0
rows, cols = len(matrix), len(matrix[0])
row_zero, col_zero = set(), set()
for row in range(rows):
for col in range(cols):
if matrix[row][col] == 0:
row_zero.add(row)
col_zero.add(col)
for row in range(rows):
for col in range(cols):
if row in row_zero or col in col_zero:
matrix[row][col] = 0
- Spiral Matrix - https://leetcode.com/problems/spiral-matrix/
# Init location for 4 side of the matrix, traverse each side and update
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
left, right = 0, len(matrix[0]) - 1
top, bot = 0, len(matrix) - 1
res = []
while left <= right and top <= bot:
for i in range(left, right+1):
res.append(matrix[top][i])
top+=1
for i in range(top, bot+1):
res.append(matrix[i][right])
right-=1
if not left <= right or not top <= bot:
break
for i in range(right, left-1, -1):
res.append(matrix[bot][i])
bot-=1
for i in range(bot, top-1, -1):
res.append(matrix[i][left])
left+=1
return res
- Rotate Image - https://leetcode.com/problems/rotate-image/
# O(N2) solution, at each iteration sequentially swap 4 corner, and update location for the new corner
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
left, right = 0, len(matrix) - 1
while left < right:
for i in range(right-left):
top, bottom = left, right
topLeft = matrix[top][left+i]
matrix[top][left+i] = matrix[bottom-i][left]
matrix[bottom-i][left] = matrix[bottom][right-i]
matrix[bottom][right-i] = matrix[top+i][right]
matrix[top+i][right] = topLeft
left +=1
right -=1
Tree
- Maximum Depth of Binary Tree - https://leetcode.com/problems/maximum-depth-of-binary-tree/
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
if not root.left and not root.right:
return 1
left = self.maxDepth(root.left)
right = self.maxDepth(root.right)
return 1 + max(left, right)
- Same Tree - https://leetcode.com/problems/same-tree/
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if not p and not q:
return True
elif not p and q:
return False
elif p and not q:
return False
else:
if p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right):
return True
return False
- Invert/Flip Binary Tree - https://leetcode.com/problems/invert-binary-tree/
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return
left = self.invertTree(root.left)
right = self.invertTree(root.right)
root.left, root.right = right, left
return root
- Binary Tree Maximum Path Sum - https://leetcode.com/problems/binary-tree-maximum-path-sum/
# Calculate all the path sum, both left and right
# Have an array outside to store all the result
# The helper only return the max path res+left or res+right but store everything in result
def maxPathSum(self, root: Optional[TreeNode]) -> int:
result = []
def helper(node):
if not node:
return float("-inf")
left = helper(node.left)
right = helper(node.right)
result.append(left)
result.append(right)
res = node.val
result.append(res+left+right)
res = max(res, res+left, res+right)
result.append(res)
return res
helper(root)
return max(result)
- Binary Tree Level Order Traversal - https://leetcode.com/problems/binary-tree-level-order-traversal/
# Tree BFS with queue
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
result = []
if not root:
return result
queue = []
queue.append(root)
while queue:
cur_level = []
cur_len = len(queue)
for i in range(cur_len):
node = queue.pop(0)
cur_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(cur_level)
return result
- Serialize and Deserialize Binary Tree - https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
- Subtree of Another Tree - https://leetcode.com/problems/subtree-of-another-tree/
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
if not root and not subRoot:
return True
if not root:
return False
def sameTree(root1, root2):
if not root1 and not root2:
return True
if (not root1 and root2) or (not root2 and root1):
return False
if root1.val != root2.val:
return False
return sameTree(root1.left, root2.left) and sameTree(root1.right, root2.right)
if not sameTree(root, subRoot):
return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
return True
- Construct Binary Tree from Preorder and Inorder Traversal - https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
# Root is the first element in preorder
# Find the root in the inorder, the left of it will be the traversal of left subtree and the right will be the traversal of right subtree
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder or not inorder:
return None
root = TreeNode(preorder[0])
rootIndex = inorder.index(preorder[0])
root.left = self.buildTree(preorder[1:rootIndex+1], inorder[:rootIndex])
root.right = self.buildTree(preorder[rootIndex+1:], inorder[rootIndex+1:])
return root
- Validate Binary Search Tree - https://leetcode.com/problems/validate-binary-search-tree/
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def check(node, lower, upper):
if not node:
return True
if not (node.val > lower and node.val < upper):
return False
return check(node.left, lower, node.val) and check(node.right, node.val, upper)
return check(root, float("-inf"), float("inf"))
- Kth Smallest Element in a BST - https://leetcode.com/problems/kth-smallest-element-in-a-bst/
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
left_views = self.dfs(root, [])
return left_views[k-1]
def dfs(self, node, result):
if not node:
return result
result = self.dfs(node.left, result)
result.append(node.val)
result = self.dfs(node.right, result)
return result
- Lowest Common Ancestor of BST - https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
while root:
if root.val == p.val or root.val == q.val:
return root
if p.val <= root.val and q.val <= root.val:
root = root.left
elif p.val >= root.val and q.val >= root.val:
root = root.right
elif (p.val < root.val and q.val > root.val) or (p.val > root.val and q.val < root.val):
return root
- Diameter of Binary Tree - https://leetcode.com/problems/diameter-of-binary-tree/
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
diameter = 0
def dfs(node):
nonlocal diameter
if not node:
return 0
left = dfs(node.left)
right = dfs(node.right)
diameter = max(diameter, left+right)
return 1 + max(left, right)
dfs(root)
return diameter
- Balanced Binary Tree - https://leetcode.com/problems/balanced-binary-tree/
def isBalanced(self, root: Optional[TreeNode]) -> bool:
if not root or (root and not root.left and not root.right):
return True
flag = False
def dfs(node):
nonlocal flag
if not node:
return 0
left = dfs(node.left)
right = dfs(node.right)
if abs(left-right) > 1:
flag = True
return 1 + max(left, right)
dfs(root)
if flag:
return False
return True
- Binary Tree Right Side View - https://leetcode.com/problems/binary-tree-right-side-view/
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
queue = []
result = []
queue.append(root)
while queue:
cur_level = []
len_queue = len(queue)
for i in range(len_queue):
node = queue.pop(0)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
cur_level.append(node.val)
result.append(cur_level[-1])
return result
- Count good nodes in binary tree - https://leetcode.com/problems/count-good-nodes-in-binary-tree/
# Keep a stack to store max value for the current path, once we done process the current path, we can remove the newest max that is only available in this path
def goodNodes(self, root: TreeNode) -> int:
count = 0
maxSoFar = [float("-inf")]
def dfs(node):
nonlocal count
if not node:
return None
flag = False
if node.val >= maxSoFar[-1]:
maxSoFar.append(node.val)
count +=1
flag = True
dfs(node.left)
dfs(node.right)
if flag:
maxSoFar.pop()
dfs(root)
return count
Tries
Implement Trie (Prefix Tree) - https://leetcode.com/problems/implement-trie-prefix-tree/
- Word Search II - https://leetcode.com/problems/word-search-ii/
- Add and Search Word - https://leetcode.com/problems/add-and-search-word-data-structure-design/
Backtracking
def subsets(self, nums: List[int]) -> List[List[int]]:
result = []
workingSet = []
def dfs(i):
if i >= len(nums):
result.append(workingSet.copy())
return
workingSet.append(nums[i])
dfs(i+1)
workingSet.pop()
dfs(i+1)
dfs(0)
return result
- Permutations - https://leetcode.com/problems/permutations/
- Subsets 2 - https://leetcode.com/problems/subsets-ii/
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums.sort()
subset = []
result = []
def dfs(index):
if index == len(nums):
result.append(subset.copy())
return
subset.append(nums[index])
dfs(index+1)
subset.pop()
while index+1 < len(nums) and nums[index] == nums[index+1]:
index+=1
dfs(index+1)
dfs(0)
return result
- Palindrome Partitioning - https://leetcode.com/problems/palindrome-partitioning/
- Letter Combination of a phone number - https://leetcode.com/problems/letter-combinations-of-a-phone-number/
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
digitLetter = {
"2": ["a", "b", "c"],
"3": ["d", "e", "f"],
"4": ["g", "h", "i"],
"5": ["j", "k", "l"],
"6": ["m", "n", "o"],
"7": ["p", "q", "r", "s"],
"8": ["t", "u", "v"],
"9": ["w", "x", "y", "z"]
}
result = []
working = []
def dfs(digitIndex):
if digitIndex >= len(digits):
result.append("".join(working))
return
letters = digitLetter[digits[digitIndex]]
for i in range(len(letters)):
working.append(letters[i])
dfs(digitIndex+1)
working.pop()
dfs(0)
return result
- Word Search - https://leetcode.com/problems/word-search/
def exist(self, board: List[List[str]], word: str) -> bool:
rows, cols = len(board), len(board[0])
path = set()
def dfs(row, col, index):
if index == len(word):
return True
if (
row not in range(rows) or
col not in range(cols) or
(row, col) in path or
board[row][col] != word[index]
):
return False
path.add((row, col))
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
res = False
for row_dir, col_dir in directions:
next_row = row + row_dir
next_col = col + col_dir
res = res or dfs(next_row, next_col, index+1)
path.remove((row, col))
return res
for row in range(rows):
for col in range(cols):
if dfs(row, col, 0):
return True
return False
- Combination Sum - https://leetcode.com/problems/combination-sum/
# Backtracking, intuition is that dfs(0) will generate every solution that involves nums[0] already so when we call dfs(1) we elimiate nums[0] out of the choice pools, thats why we need the `index` as argument
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
working = []
result = []
def dfs(index):
if sum(working) == target:
result.append(working.copy())
return
if sum(working) > target:
return
for i in range(index, len(candidates)):
working.append(candidates[i])
dfs(i)
working.pop()
dfs(0)
return result
- Combination Sum 2 - https://leetcode.com/problems/combination-sum-ii/
# The different here is that we can only use each number only once, and to avoid duplicates. So we sort the candidates array first to reliably avoid process the same value twice, and during the iterations, we also don't want to re-include the current element so we use `i+1` for the next iterations
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
result = []
candidates.sort()
working = []
def dfs(index):
if sum(working) == target:
result.append(working.copy())
return
if sum(working) > target:
return
prev = -1
for i in range(index, len(candidates)):
if candidates[i] == prev:
continue
working.append(candidates[i])
dfs(i+1)
working.pop()
prev = candidates[i]
dfs(0)
return result
- Word Search - https://leetcode.com/problems/word-search/
def exist(self, board: List[List[str]], word: str) -> bool:
rows, cols = len(board), len(board[0])
path = set()
def dfs(row, col, index):
if index == len(word):
return True
if (
row not in range(rows) or
col not in range(cols) or
(row, col) in path or
board[row][col] != word[index]
):
return False
path.add((row, col))
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
res = False
for row_dir, col_dir in directions:
next_row = row + row_dir
next_col = col + col_dir
res = res or dfs(next_row, next_col, index+1)
path.remove((row, col))
return res
for row in range(rows):
for col in range(cols):
if dfs(row, col, 0):
return True
return False
Heap
- https://leetcode.com/problems/kth-largest-element-in-a-stream/
- https://leetcode.com/problems/last-stone-weight/
- https://leetcode.com/problems/k-closest-points-to-origin/
- https://leetcode.com/problems/kth-largest-element-in-an-array/
- https://leetcode.com/problems/task-scheduler/
- https://leetcode.com/problems/design-twitter/
- Merge K Sorted Lists - https://leetcode.com/problems/merge-k-sorted-lists/
- Find Median from Data Stream - https://leetcode.com/problems/find-median-from-data-stream/